package com.sheng.leetcode.year2022.month03.day09;

import org.junit.Test;

/**
 * @Date 2022/3/9 10:12
 * @author liusheng
 * 798. 得分最高的最小轮调
 * 给你一个数组 nums，我们可以将它按一个非负整数 k 进行轮调，这样可以使数组变为
 * [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]] 的形式。此后，任何值小于或等于其索引的项都可以记作一分。
 *
 * 例如，数组为 nums = [2,4,1,3,0]，我们按 k = 2 进行轮调后，它将变成 [1,3,0,2,4]。这将记为 3 分，
 * 因为 1 > 0 [不计分]、3 > 1 [不计分]、0 <= 2 [计 1 分]、2 <= 3 [计 1 分]，4 <= 4 [计 1 分]。
 * 在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调下标 k 。如果有多个答案，返回满足条件的最小的下标 k 。
 * 示例 1：
 *
 * 输入：nums = [2,3,1,4,0]
 * 输出：3
 * 解释：
 * 下面列出了每个 k 的得分：
 * k = 0,  nums = [2,3,1,4,0],    score 2
 * k = 1,  nums = [3,1,4,0,2],    score 3
 * k = 2,  nums = [1,4,0,2,3],    score 3
 * k = 3,  nums = [4,0,2,3,1],    score 4
 * k = 4,  nums = [0,2,3,1,4],    score 3
 * 所以我们应当选择 k = 3，得分最高。
 * 示例 2：
 *
 * 输入：nums = [1,3,0,2,4]
 * 输出：0
 * 解释：
 * nums 无论怎么变化总是有 3 分。
 * 所以我们将选择最小的 k，即 0。
 *
 * 提示：
 * 1 <= nums.length <= 105
 * 0 <= nums[i] < nums.length
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/smallest-rotation-with-highest-score
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0798 {

    @Test
    public void test01(){
        //int nums[] = {2,3,1,4,0};
        //int nums[] = {1,3,0,2,4};
        int[] nums = {4,1,4,0,0};
        int ints = new Solution().bestRotation(nums);
        System.out.println(ints);
    }
}
class Solution {
    public int bestRotation(int[] nums) {
        int length = nums.length;
        int[] counts = new int[length];
        int ints = 0;
        for (int i = 0; i < length; i++) {
            int k = i;
            int z = 0;
            int[] copyNums = new int[length];
            int count = 0;
            for (int j = 0; j < length; j++) {
                if (k <= nums.length - 1) {
                    copyNums[j] = nums[k];
                    k++;
                } else {
                    copyNums[j] = nums[z];
                    z++;
                }
                if (copyNums[j] <= j) {
                    count++;
                }
            }
            counts[i] = count;
            for (int j = 0; j < length; j++) {
                System.out.print(copyNums[j] + "\t");
            }
            System.out.println("-----" + count);
        }
        for (int j = 0; j < length; j++) {
            System.out.print(counts[j] + "\t");
        }
        System.out.println();
        int max = counts[0];
        for (int j = 1; j < length; j++) {
            if (max < counts[j]) {
                max = counts[j];
                ints = j;
            }
        }
        return ints;
    }
}
//class Solution {
//    public int bestRotation(int[] nums) {
//        int n = nums.length;
//        int[] diffs = new int[n];
//        for (int i = 0; i < n; i++) {
//            int low = (i + 1) % n;
//            int high = (i - nums[i] + n + 1) % n;
//            diffs[low]++;
//            diffs[high]--;
//            if (low >= high) {
//                diffs[0]++;
//            }
//        }
//        int bestIndex = 0;
//        int maxScore = 0;
//        int score = 0;
//        for (int i = 0; i < n; i++) {
//            score += diffs[i];
//            if (score > maxScore) {
//                bestIndex = i;
//                maxScore = score;
//            }
//        }
//        return bestIndex;
//    }
//}

